1. Field of the Invention
The present invention relates to an equalizer, and more particularly, to a Viterbi equalizer.
2. Description of the Prior Art
In information systems, inter-symbol interference (ISI) is a common phenomenon. The primary cause of ISI is multipath propagation. For example, when a transmission end transmits a symbol D(1), the symbol D(1) may pass through different paths before arriving at a receiving end. Since the symbol D(1) passing through the different paths corresponds to different delayed times, the receiving end may detect energy of the symbol D(1) at different times. Hence, when the transmission end transmits sequentially, for example, a plurality of symbols D(2), D(3), D(4) . . . to the receiving end, the symbols can be affected by the previously transmitted symbol D(1).
To further explain the multipath propagation phenomenon, please refer to FIG. 1. FIG. 1 illustrates a diagram of an equivalent model of a multipath channel. As shown in FIG. 1, the model 10 includes a plurality of delay units 12, 14, a plurality of multipliers 22, 24, 26, and an adder 28. If the symbol transmitted by the transmission end is represented as D(k), and through a tapped delay line model of the multipath channel with coefficients a0, a1, . . . , an, then a signal R(k) detected by the receiving end can be represented in the formula listed below:
                              R          ⁡                      (            k            )                          =                              ∑                          i              =              0                        n                    ⁢                                    D              ⁡                              (                                  k                  -                  i                                )                                      *            a            ⁢                                                  ⁢            i                                              Formula        ⁢                                  ⁢                  (          1          )                    
According to Formula (1), if the coefficients a0, a1, a2, of the tapped delay line module are 1, 0.2, −0.4 respectively, and the remaining coefficients are all zeros, then the influence of symbols D(k−1), D(k−2) on the received signal R(k) constitutes ISI. Because the ratio of the symbols D(k), D(k−1), D(k−2) affecting the received signal R(k) is 1:0.2:−0.4, the multipath channel of the above-mentioned can be represented as a tapped delay line module with coefficients of [1 0.2 −0.4]. When the length of the tapped delay line module becomes longer (i.e., there are more non-zero coefficients), the ISI caused by a certain transmission symbol will last longer.
Equalizers emerged to solve the ISI problem. There are two types of most commonly seen equalizers. The first type of equalizer is the decision feedback equalizer. Please refer to FIG. 2. FIG. 2 illustrates a functional block diagram of a decision feedback equalizer 30. The decision feedback equalizer 30 includes a subtracter 32, a decision unit 34, and a feedback filter 60. The feedback filter 60 is utilized for generating a reconstructed interference signal SI. Then the subtracter 32 subtracts the reconstructed interference signal SI from a received signal SR to generate a calculation signal SR'. Lastly, the decision unit 34 generates a decision signal SD according to the value of the calculation signal SR'. At this point, the decision output, or the decision signal SD, is outputted as an equalized signal generated by the decision feedback equalizer 30. As the equalized signal approaches the received signal without multipath propagation, the equalizer is proved of better efficiency.
The feedback filter 60 generating the reconstructed interference signal SI includes a plurality of delay units 62, 64, 66, 68, a plurality of multipliers 72, 74, 76, 78, and an adder 82. The coefficients b0, b1, b2, . . . bm with the multipliers 78, 76, 74, 72 can be pre-determined through techniques such as channel estimation or adaptive filtering. Please note that, in an effort to simplify the calculation process in the following examples, the coefficient b0 is set to 1. Furthermore, the coefficients b0, b1, b2, . . . , bm are calculated to approach the coefficients a0, a1, . . . , an as illustrated in FIG. 1 of the tapped delay line module of the environmental multipath channel. Thus, to provide a more detailed explanation, please assume that bk is equal to ak for k=0˜n and bk is 0 for k≧n+1 . Hence, the feedback filter 60 can utilize the plurality of decision signals SD previously generated and the coefficients b0, b1, b2, . . . bm, to calculate a reconstructed interference signal SI(K), i.e., the ISI of the received signal SR(k). The calculation of the feedback filter 60 can be represented by the formula listed below:
                                          S            I                    ⁡                      (            k            )                          =                              ∑                          i              =              1                        m                    ⁢                                                    S                D                            ⁡                              (                                  k                  -                  i                                )                                      *            b            ⁢                                                  ⁢            i                                              Formula        ⁢                                  ⁢                  (          2          )                    
The decision feedback equalizer 30 described earlier does suffer from disadvantages. Particularly, the decision feedback equalizer 30 eliminates all the interferences in the received signal, but in practice, retaining a portion of the interference allows the received signal to retain more energy, and said energy can help the receiving end to perform a more accurate determination such that a more accurate received signal can be obtained. It is well known that the decision feedback equalizer 30 cannot eliminate interference sensibly, therefore, there exists room for improvement regarding its application.
The second type of equalizer is the Viterbi equalizer. The primary mechanism of the Viterbi equalizer is to generate a trellis tree according to the multipath channel. The trellis tree can have many states. A maximum likelihood algorithm is utilized within a predetermined period of time for identifying which state is the most likely path for the received signal. Then, an equalized signal is generated according to the path selected (i.e., the most likely path), and becomes the equalizing result of the received signal within the predetermined period of time. Operation and realization of the Viterbi equalizer can be referenced from many sources, including: G. D. Forney, Jr. “Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference” IEEE Transactions on Information Theory, Vol. IT-18, No. 3 pp. 363-378 May 1972, A. J. Viterbi and J. K. Omura (1979) “Principles of Digital Communication and Coding” McGraw-Hill Kogakusha Ltd, Tokyo, G. Ungerboeck “Channel Coding with Multilevel/Phase Signals” IEEE Transactions on Information Theory, Vol. IT-28, No. 1, pp. 56-67, January 1982, A. Duel-Hallen and C. Heegard “Delayed Decision-Feedback Sequence Estimation” IEEE Transactions on Telecommunications, Vol. COM-37, No. 5, pp. 48-436, May 1989, A. Duel-Hallen and C. Heegard “Reduced-State Sequence Estimation with Set Partition and Decision Feedback” IEEE Transactions on Telecommunications, Vol. 52, No. 9, pp. 1541-1562, November 1973, J. Hagenauer and P. Hoeher “A Viterbi Algorithm with Soft-Decision Output and its Application” IEEE Globecom, pp. 1680-1686, 1989. Please note that there are numerous implementations for the Viterbi equalizer, and the above-listed merely serve as examples.
The architecture of the trellis tree of the Viterbi equalizer corresponds to all possible ISI combinations [D(k−1) D(k−2) . . . D(k−N)] of the multipath channel, such as: [D(k−1)], [D(k−2)], [D(k−1) D(k−3)], or [D(k−1) D(k−2) D(k−3)], etc. The state count of the trellis tree and the length of the tapped delay line module demonstrate an exponential relationship; in another words, when the length of the tapped delay line module is P, and all symbol count is M, the state count of the trellis tree is MP. As a result, when the delay spread of the multipath channel becomes more severe, the length of the tapped delay line module increases accordingly, which translates to a drastic ramp in the complexity of the trellis tree. Consequently, the amount of calculation of the Viterbi equalizer increases significantly.
In general, the Viterbi equalizer seeks a sequence from all of the possible sequences generated that most resembles the received signal in generating an equalizing result. Although the conventional Viterbi equalizer can make a full use of the energy of the received signal, and at the same time, maintain a more satisfactory anti-ISI effect than others, the amount of calculation of the conventional Viterbi equalizer exhibits an exponential growth in response to an increase in the length of the tapped delay line module, or the worsening of the delay spread of the multipath channel.